package leetcode;

public class LongestRepeatCharReplace {

	// Given a string that consists of only uppercase English letters, you can replace any letter in the 
	// string with another letter at most k times. 
	// Find the length of a longest substring containing all repeating letters you can get after 
	// performing the above operations.
	
	//firstly, let us figure out how to change the string to the equal characters
	
	// length of the entire string - number of times of the maximum occurring character in the string
	
	// Given this, we can apply the at most k changes constraint and maintain a sliding window such that
	
	// (length of substring - number of times of the maximum occurring character in the substring) <= k
	
	//so brilliant
    public int characterReplacement(String s, int k) {
    	if(s == null){
    		return 0;
    	}
        int[] count = new int[26];
        int length = s.length();
        int start = 0;
        //记录出现的最大字符
        int maxCount = 0;
        int res = 0;
        for (int end = 0; end < length; end++) {
        	//  ++count[s.charAt(end) - 'A'] 将该字符的计数加1
        	maxCount = Math.max(maxCount, ++count[s.charAt(end) - 'A']);
        	//超过滑动窗口
        	while (end - start + 1 - maxCount > k) {
        		count[s.charAt(start) - 'A']--;
        		start++;
        	}
        	//此时在此滑动窗口里的字符可以变换k次以内得到全部相等的字符
        	res = Math.max(res, end - start + 1);
		}
        return res;
    }
}
